package com.wtgroup.demo.mianshi.算法.动态规划;

import com.wtgroup.demo.common.util.RandomUtil;

/**
 * <<算法导论>> P219
 *
 * @author dafei
 * @version 0.1
 * @date 2021/4/15 18:25
 */
public class D_钢条切割 {
    public static void main(String[] args) {
        // int[] inputs = {4, 10};
        int[] inputs = RandomUtil.randomArray(10, 1, 11);
        // int[] inputs = {20};
        for (int input : inputs) {
            System.out.println("------------------------------------");
            int res1 = new Solution_1().process(input);
            System.out.println(res1);
            int res2 = new Solution_2().process(input);
            System.out.println(res2);
            int res3 = new Solution_Pack().process(input);
            System.out.println(res2);
            int res4 = new Solution_T20210511().process(input);
            System.out.println(res4);
            int res5 = new Solution_T().run(input);
            System.out.println(res5);
        }

        /*
        * 背包思路, 可以接受必价格表里更长的输入.
        * */
    }


    public static final int LEN = 10;
    public static final int[] PRICES = new int[LEN + 1];

    static {
        // 钢条长度->价格
        // 长度连续的, 每个长度都有对应的价格
        PRICES[1] = 1;
        PRICES[2] = 5;
        PRICES[3] = 8;
        PRICES[4] = 9;
        PRICES[5] = 10;
        PRICES[6] = 17;
        PRICES[7] = 17;
        PRICES[8] = 20;
        PRICES[9] = 24;
        PRICES[10] = 30;
    }

    /**
     * 自顶向下
     * <p>
     * 需要备忘录.
     * i 段, i后
     *
     * @param n 要<= LEN
     */
    private static class Solution_1 {
        public static int process(int n) {
            int[] memo = new int[n + 1];
            return func(n, memo);
        }

        public static int func(int n, int[] memo) {
            if (memo[n] > 0) {
                return memo[n];
            }

            for (int i = 1; i <= n; i++) {
                memo[n] = Math.max(PRICES[i] + func(n - i, memo), memo[n]);
            }

            return memo[n];
        }
    }


    /**
     * 自底向上
     * 不需要备忘录
     * <p>
     * 更巧妙呀!
     */
    private static class Solution_2 {

        public int process(int n) {
            int[] dp = new int[n + 1];
            // rest 剩余长度, item 短钢条
            for (int rest = 1; rest <= n; rest++) {
                for (int item = 1; item <= rest; item++) { // 暗含 item <= rest , 即选择的短钢条长度要小于剩余的总长度
                    dp[rest] = Math.max(PRICES[item] + PRICES[rest - item], dp[rest]);
                }
            }

            return dp[n];
        }
    }


    /**
     * 看做一个完全背包问题来解.
     * 给定整体钢条长度相当于背包容量.
     * 不同小段长度相当于该物品的重量, 价格相当于收益.
     * 不超过容量的前提下, 挑选商品, 获取最大收益.
     */
    private static class Solution_Pack {

        public int process(int n) {
            int[] dp = new int[n + 1];
            // 相当于物品数
            int len = PRICES.length;
            for (int item = 1; item < len; item++) {
                for (int rest = 1; rest <= n; rest++) {
                    // 物品长度小于等于当前总长度
                    if (item <= rest) {
                        dp[rest] = Math.max(PRICES[item] + dp[rest - item], dp[rest]);
                    } // else 不取, 沿用上次状态
                }
            }

            return dp[n];
        }
    }

    // 暴力递归
    static class Solution_T20210511 {
        int process(int n) {
            if (n==0) {
                return 0;
            }

            int ans = 0;
            for (int i = 1; i <= n; i++) {
                ans = Math.max(ans, PRICES[i] + process(n - i));
            }
            return ans;
        }
    }

    /**
     * 错误!!! 暴力递归一层循环搞定了. 但是转为动归时, 发现一个普遍位置 i 依赖 n-i,
     * 而 n-i 有依赖 (n-(n-i)=i 位置, 从而出现"循环依赖".
     * 此时, 考虑是不是少了一层循环.
     *
     * 哎...痛苦, 纠结...
     */
    static class Solution_T {
        int run(int n) {

            int[] dp = new int[n+1];
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= i; j++) {
                    dp[i] = Math.max(dp[i], PRICES[j] + dp[i - j]);
                }
            }

            return dp[n];
        }
    }
}
